package com.wenyl.tree;

import lombok.Data;

/**
 * 二叉搜索树的实现类
 */
@Data
public class BinarySearchTree {
    /**
     * 二叉搜索树的根节点
     */
    private BSTNode root;

    /**
     * 向二叉搜索树中插入一个新的节点
     * @param data 要插入的数据
     */
    public void insert(int data){
        if (root == null) {
            root = new BSTNode(data);
            return;
        }
        BSTNode currentNode = root;
        while (currentNode != null) {
            if (data < currentNode.getData()) {
                if (currentNode.getLeftChild() == null) {
                    currentNode.setLeftChild(new BSTNode(data));
                    return;
                }
                currentNode = currentNode.getLeftChild();
            } else if (data > currentNode.getData()) {
                if (currentNode.getRightChild() == null) {
                    currentNode.setRightChild(new BSTNode(data));
                    return;
                }
                currentNode = currentNode.getRightChild();
            } else {
                System.out.println("数据重复，插入失败");
                return;
            }
        }
    }

    /**
     * 从二叉搜索树中删除指定数据的节点
     * @param data 要删除的数据
     */
    public void delete(int data){
        if (root == null) {
            System.out.println("树为空，删除失败");
            return;
        }
        BSTNode currentNode = root;
        BSTNode parentNode = null;
        while (currentNode != null) {
            if (data < currentNode.getData()) {
                parentNode = currentNode;
                currentNode = currentNode.getLeftChild();
            } else if (data > currentNode.getData()) {
                parentNode = currentNode;
                currentNode = currentNode.getRightChild();
            } else {
                break;
            }
        }    
        if (currentNode == null) {
            System.out.println("数据不存在，删除失败");
            return;
        }
        // 叶子节点
        if (currentNode.getLeftChild() == null && currentNode.getRightChild() == null) {
            if(parentNode == null){
                root = null;
                return;
            }
            if (parentNode.getLeftChild() == currentNode) {
                parentNode.setLeftChild(null);
            } else {
                parentNode.setRightChild(null);
            }
            return;
        }
        // 只有右子树
        else if(currentNode.getLeftChild() == null && currentNode.getRightChild() != null){
            if(parentNode == null){
                root = currentNode.getRightChild();
                currentNode.setRightChild(null);
                return;
            }
            if(parentNode.getLeftChild() == currentNode){
                parentNode.setLeftChild(currentNode.getRightChild());
            }
            if(parentNode.getRightChild() == currentNode){
                parentNode.setRightChild(currentNode.getRightChild());
            }
            currentNode.setRightChild(null);
            return;
        }
        // 只有左子树
        else if(currentNode.getLeftChild() != null && currentNode.getRightChild() == null){
            if(parentNode == null){
                root = currentNode.getLeftChild();
                currentNode.setLeftChild(null);
                return;
            }

            if(parentNode.getLeftChild() == currentNode){
                parentNode.setLeftChild(currentNode.getLeftChild());
            }
            if(parentNode.getRightChild() == currentNode){
                parentNode.setRightChild(currentNode.getLeftChild());
            }
            currentNode.setLeftChild(null);
            return;
        }
        // 左右子树都有
        else {
            BSTNode rightMinNode = findRightMinNode(currentNode);
            rightMinNode.setLeftChild(currentNode.getLeftChild());
            // 如果右子树最小节点不是当前节点的右子树，则将右子树最小节点的右子树设置为当前节点的右子树
            if(rightMinNode != currentNode.getRightChild()){
                rightMinNode.setRightChild(currentNode.getRightChild());
            }
            // 如果父节点为空，说明要删除的节点是根节点
            if(parentNode == null){
                root = rightMinNode;
            }else{
                if(parentNode.getLeftChild() == currentNode){
                    parentNode.setLeftChild(rightMinNode);
                }else{
                    parentNode.setRightChild(rightMinNode);
                }
            }
            // 将当前节点从树中移除,等待垃圾回收
            currentNode.setLeftChild(null);
            currentNode.setRightChild(null);
            return;
        }
    }

    /**
     * 查找右子树中的最小节点
     * @param currentNode 当前节点
     * @return 右子树中的最小节点
     */
    private BSTNode findRightMinNode(BSTNode currentNode) {
        BSTNode minNode = currentNode.getRightChild();
        BSTNode parentNode = currentNode;
        
        while (minNode.getLeftChild() != null) {
            parentNode = minNode;
            minNode = minNode.getLeftChild();
        }
        // 将最小节点从右子树中移除,用来替换被删除的节点
        // 若最小节点就是删除节点的右子树，则不做处理
        if(parentNode != currentNode){
            parentNode.setLeftChild(minNode.getRightChild());
        }
        return minNode;
    }

    /**
     * 前序遍历二叉树
     * 遍历顺序：根节点 -> 左子树 -> 右子树
     * @param currentNode 当前节点
     */
    public void preOrderTraversal(BSTNode currentNode){
        if(currentNode == null){
            return;
        }
        System.out.print(currentNode.getData()+" ");
        preOrderTraversal(currentNode.getLeftChild());
        preOrderTraversal(currentNode.getRightChild());
    }

    /**
     * 中序遍历二叉树
     * 遍历顺序：左子树 -> 根节点 -> 右子树
     * @param currentNode 当前节点
     */
    public void inOrderTraversal(BSTNode currentNode){
        if(currentNode == null){
            return;
        }
        inOrderTraversal(currentNode.getLeftChild());
        System.out.print(currentNode.getData()+" ");
        inOrderTraversal(currentNode.getRightChild());
    }

    /**
     * 后序遍历二叉树
     * 遍历顺序：左子树 -> 右子树 -> 根节点
     * @param currentNode 当前节点
     */
    public void postOrderTraversal(BSTNode currentNode){
        if(currentNode == null){
            return;
        }
        postOrderTraversal(currentNode.getLeftChild());
        postOrderTraversal(currentNode.getRightChild());
        System.out.print(currentNode.getData()+" ");
    }
}

/**
 * 二叉搜索树的节点类
 */
@Data
class BSTNode{
    /**
     * 节点存储的整数数据
     */
    private int data;
    
    /**
     * 左子节点
     */
    private BSTNode leftChild;
    
    /**
     * 右子节点
     */
    private BSTNode rightChild;
    
    /**
     * 构造一个新的BSTNode
     * @param data 节点存储的整数数据
     */
    public BSTNode(int data){
        this.data = data;
    }
}
